(a) Field of the Invention
The present invention relates to a pattern matching system and a pattern matching method, and more particularly, to a system and a method for matching a pattern with a data packet processed at a high speed in a communication network equipment or system.
(b) Description of the Related Art
A communication network has evolved while newly creating a large number of services, and the requirements of users have been diversified more and more. In this connection, very much information is generated, eliminated, or stored in the network. Some of such information is security-related, and techniques thereof have also been developed. Information security threatening factors have recently appeared in networks in complicated and diversified manners. Furthermore, network accessed networking equipment and communication terminals are variously provided with functions for detecting and preventing such threatening factors. The network threatening factors may appear throughout all the layers of packets transmitted through the network. Particularly, the data should be analyzed from first to last in order to detect the factors appearing in the application layer.
Pattern matching is utilized in order to find specific information from the application layer data. That is, the application layer data are detected so as to judge whether there is a pattern to be matched with desired specific information. As the location of target information is not predetermined, the information retrieval may be terminated within a very short period of time, or occasionally continue up to the last data.
The pattern matching may be classified into two types. The first is to detect a pattern in a software manner by utilizing various forms of central processing units and memories. It is very easy with this technique to design an algorithm and to realize the algorithm in a software manner. However, such a technique depends upon the data processing speed of the central processing unit and the memory, and is somewhat limited in processing data at a high speed because it is not easy therewith to do the data processing in parallel. In order to overcome such a limitation, the second type is to detect a pattern in a hardware manner by using a content addressable memory (CAM). Such a technique utilizes the parallel processing function of the CAM, which includes a plurality of entries. The respective entries include a memory capable of storing the target data, and a comparator capable of comparing the data stored at the memory with the data input into the CAM. Furthermore, the data input into the CAM are compared with the data stored at all the entries belonging to the CAM simultaneously. With the usage of such a function of the CAM, the data may be processed at a higher speed in retrieving the specific information from the application layer data.
The pattern matching system usually includes techniques of detecting a pattern to be generated by way of a combination of strings, not being limited to the detection of simple strings. The representative is a regular expression matching technique. A regular expression is established by converting particular word sets or strings into symbols, and is used in designating an expression rule for correctly expressing a set of strings, a linguistic grammar definition, and a string to be detected.
With a conventional pattern matching system conducting the string matching for detecting strings contained in the entries of a single CAM and the regular expression matching for detecting a regular expression constructed by the detected strings, the larger the number of strings contained in the target pattern to be detected is and the longer the length of the strings contained in the target pattern is, the more rapidly state transitions pursuant to the regular expression matching increase, and accordingly, the memory included in the CAM and the memory used for the state transitions need to be significantly increased.
The above information disclosed in this Background section is only for enhancement of understanding of the background of the invention and therefore it may contain information that does not form the prior art that is already known in this country to a person of ordinary skill in the art.